1. Field
Embodiments of the invention generally relate to techniques for searchable encryption. More specifically, techniques are disclosed for updating an encrypted search index using normalized user identifiers.
2. Description of the Related Art
Cloud computing services, such as file sharing services and file storage services, allow users to store data in virtualized pools of storage that are hosted on third party servers. Users of these services may search through their documents and share access with other users in the cloud for collaborative purposes. Although cloud computing offers many benefits, security remains an important concern. For instance, a user may not want a cloud provider to be able to access or modify the user's data stored on a host server. At the same time, a user may want to be able to share data with trusted parties. To maintain privacy, the cloud service encrypts the data so that, generally, only the user may access the data and share access to others who have valid permissions. One consequence of this, however, is that encryption creates difficulty in searching through the data. That is, a cloud provider wants to provide search functionality to a user while still maintaining the encryption. A typical approach is to create a search index while the user is logged in (i.e., the data is decrypted) and to encrypt the search index when the user logs off. Encrypting the search index prevents an attacker from retrieving valuable information about the encrypted data.
However, another challenge arises in situations where there are updates to the data, and therefore the search index needs to be updated, but the user is offline (i.e., the cloud provider cannot access the user's data or the search index). For instance, some cloud providers retrieve data from third party services where a user has an account, such as an e-mail or social media service. If a person, through one of these services, sends a message to the user, the cloud provider must be able to update the user's account to reflect this in the search index. One possible solution is to wait until the user logs in to update the search index with the new data, but this approach requires the user to wait a period of time upon login for the cloud provider to finish updating before the user is able to search through documents. Instead, a server may create a new search index and encrypt the index with a new key and store it, and encrypt the key with the user's public key.
One further problem, however, is that some cloud providers may normalize the identities of people with whom a user communicates across third party web services. A cloud provider may normalize the identities (social network ID's, e-mail addresses, etc.) into an identifier that is unique to the provider and store these normalized identifiers to a table. A cloud provider must additionally protect this normalization table because the table stores information that an attacker may find useful, such as people with whom a user is communicating, their e-mail/social media data, etc. One approach is to simply encrypt the normalization table in the same manner as the cloud provider encrypts the search index. However, this solution hinders the cloud provider's ability to update the normalization table and search index when the user is offline (because only the user has the private key that may access both). Another approach is to encrypt each entry in the normalization table for quick reference. Although this solves the problem of updatability, this approach is vulnerable to dictionary attacks and frequency analyses.